// 栈
// 数组实现
class ArrayStack {
    constructor() {
        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })
        // 初始化数组
        let _store = new Array();
        /**
         * 入栈
         * 时间复杂度:O(1)
         * @param ele
         */
        this.push = function (ele) {
            _store[_size] = ele;
            _size++;
        }
        /**
         * 出栈
         * 时间复杂度:O(1)
         */
        this.pop = function () {
            if (_size <= 0) {
                throw new Error("超出栈范围");
            }
            _size--;
            let ele = _store[_size];
            return ele;
        }
        /**
         * 访问栈顶元素
         * 时间复杂度:O(1)
         */
        this.peek = function () {
            if (_size <= 0) {
                throw new Error("超出栈范围");
            }
            let ele = _store[_size - 1];
            return ele;
        }
        // 转换为数组
        this.toArray = function () {
            // 不直接返回 store ，返回store的复制对象，这样外部就无法修改到 store属性
            let newStore = new Array(this.size);
            for (let i = 0; i < this.size; i++) {
                newStore[i] = _store[i];
            }
            return newStore
        }
    }

    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}

/**
 * 链接节点
 */
class LinkedNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}


// 链表实现
class LinkedStack {
    constructor() {
        // 当前数组大小
        let _size = 0;
        Object.defineProperty(this, 'size', {
            get() {
                return _size;
            },
            set() {
                throw new Error('无法修改size属性')
            },
            configurable: false,
        })

        let _headNode = null;
        /**
         * 入栈
         * 时间复杂度:O(1)
         * @param ele
         */
        this.push = function (ele) {
            _headNode = new LinkedNode(ele, _headNode);
            _size++;
        }
        /**
         * 出栈
         * 时间复杂度:O(1)
         * @returns {any}
         */
        this.pop = function () {
            if (_headNode == null) {
                throw Error("超出栈范围")
            }
            _size--;
            let result = _headNode;
            _headNode = _headNode.next;
            result.next = null;
            return result.val;
        }
        /**
         * 访问栈顶元素
         * 时间复杂度:O(1)
         * @returns {any}
         */
        this.peek = function () {
            if (_headNode == null) {
                throw Error("超出栈范围")
            }
            return _headNode.val;
        }
        // 转换为数组
        this.toArray = function () {
            let newStore = new Array(this.size);
            let tmp = _headNode;
            let i = this.size - 1;
            while (tmp != null) {
                newStore[i] = tmp.val;
                i--;
                tmp = tmp.next;
            }
            return newStore
        }
    }

    /**
     * 元素的大小
     * 时间复杂度:O(1)
     */
    size() {
        return this.size;
    }
}
